package com.leecode.arrAndSort;

/**
 * 接雨水
 * <p>
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 */
public class RainMain {
	public static void main(String[] args) {
//		System.out.println(new RainMain().trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
//		System.out.println(new RainMain().trap(new int[]{2, 0, 2}));
		System.out.println(new RainMain().trap(new int[]{5,4,1,2}));
	}

	public int trap(int[] height) {
		//定义左的index为0,右一开始也等于左+1
		int l = 0, r = l + 1, sum = 0;
		int tempH = 1;

		//左界还在"一定"范围内就一直循环
		h:
		while (l <= height.length - 1 - 1) {
			//左高为0,乘个球的水,下一位
			if (height[l] == 0) {
				l++;
				r = l + 1;
				continue;
			}

			//尝试找合适的右,要保证r刚开始的r值<l值
			if (height[l] > height[r]) {
				r++;
				while (r <= height.length - 1) {
					//1.找出尽可能大的tempH,1.右比tempH大并"下一位右出现下降趋势" or 右已经是右边界了
					if (r==height.length - 1 || ( height[r] > tempH && height[r] > height[r + 1])  ) {
						tempH = height[r];
						sum += (tempH >= height[l] ? height[l] : tempH) * (r - l - 1);
						for (int i = l + 1; i <= r - 1; i++) {
							//可能540002,所以判断下
							sum -= height[i]>tempH?tempH:height[i];
						}

						tempH = 1;
						l = r;
						r = l + 1;
						continue h;
					}
					r++;
				}
			} else {
				//左不合适,换下一个左
				l++;
				r = l + 1;
			}

			//右界找了一圈没找到
			//"这个左界太大了",换下一个左,准备再进入while
//			l++;
//			r = l + 1;
			return sum;
		}


		return sum;
	}
}
